//
//  TopKFrequent.swift
//  LeetCodeDemo
//
//  Created by Yangdongwu on 2020/12/13.
//

import Foundation

class TopKFrequent {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var dic = [Int: Int]()
        for i in nums {
            dic[i] = (dic[i] ?? 0) + 1
        }
        let a = dic.sorted { $0.1 > $1.1 }
        var res = [Int](repeating: 0, count: k)
        for j in 0..<k {
            res[j] = a[j].key
        }
        return res
    }
}

class TopKFrequent01 {
    
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var dic = [Int: Int]()
        for i in nums {
            dic[i, default: 0] += 1
        }
        
        var keys = [Int](dic.keys)
        let index = keys.count - k
        if index < 0 {
            return []
        }
        quickSelect(&keys, dic, 0, keys.count - 1, index)
        return [Int](keys[index...])
    }
    
    func quickSelect(_ nums: inout [Int], _ dic: [Int: Int], _ left: Int, _ right: Int, _ k: Int) {
        let pivot = partition(&nums, left, right, dic)
        if pivot == k {
            return
        }
        if pivot < k {
            quickSelect(&nums, dic, pivot + 1, right, k)
        } else {
            quickSelect(&nums, dic, left, pivot - 1, k)
        }
    }
    
    func partition(_ nums: inout [Int], _ left: Int, _ right: Int, _ dic: [Int: Int]) -> Int {
        guard left < right else {
            return left
        }
        let pivot = right
        var cnt = left
        for i in left..<right {
            if dic[nums[i]]! < dic[nums[pivot]]! {
                nums.swapAt(i, cnt)
                cnt += 1
            }
        }
        nums.swapAt(cnt, pivot)
        return cnt
    }
    
    
}

class TopKFrequent02 {
    
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        
        var dic = [Int: Int]()
        for i in nums {
            dic[i, default: 0] += 1
        }
        
        var keys = [Int](dic.keys)
        let n = keys.count
        if n < k {
            return []
        }
        
        buildHeap(&keys, k - 1, dic)
        for i in k..<n {
            if dic[keys[0]]! < dic[keys[i]]! {
                keys[0] = keys[i]
                heapify(&keys, k - 1, 0, dic)
            }
        }
        
        return [Int](keys[0..<k])
    }
    
    func buildHeap(_ nums: inout [Int], _ n: Int, _ dic: [Int: Int]) {
        var i = n / 2
        while i >= 0 {
            heapify(&nums, n, i, dic)
            i -= 1
        }
    }
    
    func heapify(_ nums: inout [Int], _ n: Int, _ i: Int, _ dic: [Int: Int]) {
        var i = i
        while true {
            var minPos = i
            let left = 2 * i + 1
            if left <= n && dic[nums[left]]! < dic[nums[minPos]]! {
                minPos = left
            }
            let right = 2 * i + 2
            if right <= n && dic[nums[right]]! < dic[nums[minPos]]! {
                minPos = right
            }
            if minPos == i {
                break
            }
            nums.swapAt(i, minPos)
            i = minPos
        }
    }
    
    func test() {
        
        let nums = [1,1,1,2,2,3], k = 2
        
        let res = topKFrequent(nums, k)
        
        print(res)
        
    }
    
}


